# Full text of "Characterising planar Cayley graphs and Cayley complexes in terms of group presentations"

## See other formats

A group has a flat Cayley complex if and only if it has a VAP-free Cayley graph Agelos Georgakopoulos* Technische Universitat Graz Steyrergasse 30, 8010 Graz, Austria Abstract We prove that a Cayley graph can be embedded in the euclidean plane without accumulation points of vertices if and only if it is the 1-skeleton of a Cayley complex that can be embedded in the plane after removing some redundant simplices. 1 Introduction The study of groups that have Cayley graphs embeddable in the euclidean plane R 2 , called planar groups, has a tradition starting in 1896 with Maschke's charac- terization of the finite ones. Among the infinite planar groups, those that admit a flat Cayley complex, defined below, have received a lot of attention. They are important in complex analysis as they include the discontinuous groups of mo- tions of the euclidean and hyperbolic plane. Moreover, they are closely related to the surface groups [HJ Section 4.10]. These groups are now well understood due to the work of Macbeath [T3], Wiikie [T7], and others; see [IB] for a survejOJ Planar groups that have no flat Cayley complex are harder to analyse, and they are the subject of on-going research [31 El El 13 [H] - The assertion of the title can probably be derived from the results of [IB] . The aim of this paper is firstly, to provide an elementary proof of this assertion, avoiding the heavy machinery used in [18) , and secondly, to refine the assertion into a theorem about planar Cayley graphs, not just their groups: Theorem 1.1. A planar Cayley graph of a group T is VAP-free if and only if it is the 1-skeleton of a flat Cayley complex ofT. A planar graph is said to be Vertex- Accumulation- Point- free, or VAP-free for short, if it has an embedding in R 2 such that the images of its vertices have no accumulation point. The study of a planar graph is often simplified if one knows that the graph is VAP-free; examples range from structural graph-theory [3] to percolation theory [TJ] and the study of spectral properties [H] . A further ♦Supported by FWF grant P-19115-N18. 1 In |18l the term Cayley complex is not used but it is implicit in Theorems 4.5.6 and 6.4.7 that a group admits a flat Cayley complex if and only if it is a planar discontinuous group. 1 example is Thomassen's Theorem 12.31 below, which becomes false in the non- VAP-free case. VAP-free graphs can be characterized by a condition similar to that of Kuratowski's; see [5]. VAP-free embeddings also appear with other names in the literature, most notably "locally finite" ' . The Cayley complex A" of a group presentation P = (S, R) is the universal cover of its presentation complex, see [10) . From this we derive the simplified Cayley complex of P as follows. Firstly, for every pair of parallel edges e, e', resulting from an involution in 5, we identify e with e', glueing them together according to a homeomorphism from e to e! that maps each endvertex to itself. We remove any 2-simplices of X that were bounded by the circle e U e'; all other 2-simplices incident with e or e' are preserved. In the resulting 2-complcx A', we define two 2-simplices to be equivalent if they have the same boundary. Removing all but one of the elements of each equivalence class from A' we obtain the simplified Cayley complex of P. Equivalently, we can define the simplified Cayley complex of P = (S, R) by building the corresponding Cayley graph, identifying each pair of parallel edges into a single edge, and then for every cycle C of this graph induced by a relator in R, introducing a 2-simplcx having C as its boundary. We say that a Cayley complex is flat if the corresponding simplified Cayley complex is planar, that is, it admits an embedding into R 2 . For example, the Cayley complex of the group presentation (a | a") has n equivalent 2-simplices, while the corresponding simplified Cayley complex has only one, and is planar. As a further example, consider the presentation (a, b | b 2 , a6a _1 6). The corresponding simplified Cayley complex is a 2-way in- finite ladder with each 4-gon bounding a 2-simplex; note that this complex is planar, while the usual Cayley complex is not. These two examples show that the above simplifications of the Cayley complex are necessary to make Theo- rem 11.11 true. We prove Theorem 11.11 in the next section. In Section [3] we examine VAP- freeness as a group-theoretical invariant. Finally, in Section @] we show how VAP-freeness can be recognised in a group presentation. We will follow the terminology of [3] for graph-theoretical terms and that of [TJ [TU] for group-theoretical ones. 2 Proof of main result One of our main tools will be the (finitary) cycle space C/(G) of a graph G = (V,E), which is defined as the vector space over Z2 consisting of those subsets of E such that can be written as a sum (modulo 2) of a finite set of circuits, where a set of edges D C E is called a circuit if it is the edge set of a cycle of G. Thus Cf(G) is isomorphic to the first simplicial homology group of G over Z2 . The circuit of a closed walk W is the set of edges traversed by W an even number of times. Note that the direction of the edges is ignored when defining circuits and C/(G). In this section we will be assuming that our graphs have no parallel edges. In a Cayley graph this can be achieved by drawing, for every involution in the generating set, a single undirected edge rather than a pair of parallel edges with opposite directions. This convention affects neither planarity nor VAP- freeness, and so our assumption comes without loss of generality for the proof 2 of Theorem HHJ Our first lemma, a well-known fact which is easy to prove, relates C/(G) to group presentations. We will say that a closed walk W in G is induced by a relator R, if W can be obtained by starting at some vertex g and following the edges corresponding to the letters in R in order; note that for a given R there are several walks in G induced by R, one for each starting vertex g S V(G). Lemma 2.1. Let G = Cay(T,S) be a Cayley graph of the group T, and let (S | R) be a presentation ofT. Then the set of edge-sets of walks in G induced by relators in R generates C/(G). Conversely, if R' is a set of relations of T with letters in a generating set S such that the set of cycles of Cay(T, S) induced by R' generates C/(G), then (S | R'} is a presentation ofY. Combined with the next easy fact, this allows one to deduce group presen- tations from VAP-free embeddings of a Cayley graph. Lemma 2.2. Let G be a VAP-free plane graph. Then the set of finite face boundaries of G generates C/(G). Proof. It suffices to show that the edge-set of every cycle C of G is a sum of edge-sets of finite face boundaries. This is indeed the case, for as G is VAP-free there must be a side A of C containing only finitely many vertices, and so E(C) is the sum of the edge-sets of the face boundaries lying in A. □ The following theorem of Thomasscn generalises MacLane's classical pla- narity criterion [3l Theorem 4.5.1] to infinite VAP-free planar graphs. It will easily imply the backward implication of Theorem 11.11 A 2-basis of G is a generating set B of C/(G) such that no edge of G appears in more than two elements of B. Theorem 2.3 f [15l Section 7]). A connected graph G has a 2-basis if and only if it is planar and has a VAP-free embedding. The following fact is probably known to experts in the study of infinite vertex transitive graphs. We include a proof sketch for the convenience of the non-expert. A double-ray is a 2-way infinite path (with no repetition of vertices). Lemma 2.4. Let G be an infinite, connected, vertex transitive graph which is not a double-ray. Then for every pair of vertices x, y of G, no component of G — {x, y} is finite. Proof. To begin with, it is easy to prove that for every x 6 V(G), no component of G — {x} is finite, (1) by considering a minimal such component C and mapping x to some vertex of C. Suppose that some component C of G — {x, y} is finite, and choose x, y so as to minimise |F(G)|. We claim that the graph C has no cut- vertex. Indeed, if z G V(C) separates C, then G—{x, z} contains a component properly contained in C, contradicting the minimality of the latter. Moreover, each of x, y has at least two neighbours in C; for if y has a single neighbour y' in C, then we 3 could have replaced y by y' to obtain a separator {x, y'} cutting off a smaller component, and if y has no neighbour in C then ([T]) is contradicted. These two observations, combined with Menger's theorem [3J Theorem 3.3.1], imply that there are two independent x-y paths P, Q through C. Moreover, (at least) one of x, y, say x, is contained in an infinite subgraph A that does not meet P, Q except at x. Let z € V(C), and consider an automorphism g mapping x to z. Then, there is a vertex w — gy such that {z, w} separates G. We consider three cases. If w lies in a component C ^ C of G — {x, y}, then each of gP, gQ, gX meets both C" and C. But this is impossible since C is separated from C by x, y and the only vertices meeting more than one of gP, gQ, gX are z and w. If ui lies in C, then some component of G — {z, w} is properly contained in C contradicting its minimality. Finally, if w = y, then as the component gC of G — {z, w} cannot be smaller than C, it must contain the vertex x. Note that x is incident with an infinite component C of G — {x,y} because otherwise y contradicts ([T]). But then gC contains C", contradicting the fact that its translate C is finite. Thus, in all three cases we obtained a contradiction. This proves Lemma 12^1 □ We can now prove our main result. Proof of Theorem \l.ll For the forward implication, let G be a planar Cayley graph of the group T, with respect to the generating set <S, admitting a VAP- free embedding o. By Lemma 12.51 below, if F is a finite face boundary in er, then every translate of F is a face boundary. This means that if we let TV be the set of relations corresponding to the finite face boundaries of a incident with the group identity e, then every finite face boundary of a is induced by some element of TV , and conversely any cycle induced by some element of TV bounds a face in a. By Lemmas 12.11 and 12.21 (S \ TV) is a presentation of T. The corresponding simplified Cayley complex is planar and VAP-free since we can embed its 1-skclcton G by a and then every 2-simplcx can be embedded into the face of a bounded by the corresponding cycle. The backward implication follows easily from Thcorcm l2.3l let A be a planar simplified Cayley complex and let G be its 1-skelcton. Let B 1 be the set of closed walks in G bounding a 2-simplcx of A — in fact, these closed walks are cycles since A is planar — and let B := {E(C) \ C G B'} be the set of the corresponding edge-sets. Note that B generates C/(G) by Lemma [2.11 Moreover, since A is planar, no edge of A lies in the boundary of more than two 2-simplices. Thus B is a 2-basis of G, and so Theorem 12.31 implies that G is VAP-free. □ Lemma 2.5. Let G be an infinite vertex transitive graph with a VAP-free em- bedding o . If F is a finite face boundary in a then every image of F under any automorphism of G is a face boundary in a. Proof. Suppose to the contrary that some image F' — gF of F under an auto- morphism g is not a face boundary. Then, as o is VAP-free, one of the sides of F' contains at least one finite component C. Let N(C) be the set of vertices of F' sending an edge to C. Then F' — N(C) consists of a set of disjoint paths, 4 which we call the intervals. Note that there are at least three intervals, for if |7V(C) < 2 then Lemma \2. 41 is contradicted. We claim that no component of G — F' sends edges to more than one interval. (2) Indeed, if such a component C existed, then, by a topological argument, it would be impossible to embed G is such a way that both C and C lie in the same side of F' (Figured]), but such an embedding must be possible since F is a face boundary. Next, we claim that at most one of the intervals sends an edge to an infinite component of G — F 1 . For if there are intervals I ^ J adjacent with infinite components Cj, Cj of G — F' , then replacing I in F' by a path through C we would obtain a cycle D that separates Ci from Cj by @ (Figure [TJ . But then g~ 1 /, .g~ 1 J must lie in distinct sides of g~ x F> since F = g~ x F' and F is a face boundary, contradicting the fact that a is VAP-frcc. Figure 1: A contradictory situation in the proof of Lemma [2.51 Thus our claim is proved, implying that there is a unique interval I adjacent with the infinite component of G—F'. This fact, combined with ©, implies that deleting the vertices x, y € N(C) bounding / leaves a finite component, namely the component of G— {x, y} containing C. But this contradicts Lemma [2^41 □ 3 VAP-freeness as a group-theoretical invariant A planar group can admit both VAP-free and non-VAP-free Cayley graphs. For example, the Cayley graph corresponding to the presentation (a, b \ b 2 ,abati), of the infinite dihedral group, is VAP-free planar, but adding the redundant generator c — ab keeps the Cayley graph planar and makes it non-VAP-free as the reader can check. Thus VAP-freeness is not group-theoretical invariant in general. However, it becomes an invariant if one only considers 3-connected Cayley graphs: Theorem 3.1. If a group T has a 3-connected VAP-free planar Cayley graph and a group A has a 3-connected non-VAP-free planar Cayley graph, then T is not isomorphic to A. Before proving this let us see a further example showing that it is necessary that both graphs in the assertion be 3-connected. Consider the Cayley graph 5 corresponding to the presentation (a, b | a 4 ,6 4 ). This is a free product of 4- cycles, and it is easy to see that it has a VAP-free embedding and that its connectivity is 1. Now add the redundant generators c = ab and d = a 2 b 2 a 2 . Note that d 2 = 1. Figure [2] shows that the corresponding Cayley graph is still planar, and it is easy to check that it is 3-connected. The given embedding is not VAP-free. It now follows easily from the following classical result, proved by Whitney [TH Theorem 11] for finite graphs and by Imrich (TTJ for infinite ones, that no embedding of this graph is VAP-free. Theorem 3.2. Let G be a 3-connected graph embedded in the plane. Then every automorphism of G maps each facial path to a facial path. We will need a few lemmas for the proof of Theorem 13.11 Lemma 3.3. Let G be a 2-connected planar graph and let oj, ip be distinct ends of G. Then there is a cycle C in G that separates oj from ip, i.e. every double-ray with a tail in uj and a tail ip has a vertex in C . Proof. Fix an embedding a of G. Consider a finite set of vertices S = {s± , S2 , . . . , Sfc} separating oj from ip, and let C\ be a cycle containing s\, S2', such a cycle exists since G is 2-connected. If C\ does not separate oj from ip then both ends lie in one of the sides of C±, the outside say. Note that some vertex of 5* must also lie outside C\, for otherwise every double-ray with a tail in u> and a tail ip would have to go through C\ to meet S, contradicting the fact that C\ does not separate oj from ip. So pick the least index j such that Sj lies outside C\. Now consider two independent paths P\ , P2 from Sj to C\ , and let A be the region of R 2 \{Ci U P\ U P2] containing rays in oj. The boundary of A is a cycle C2 containing P1UP2 and a subpath of C\. Note that no element of {si, S2, • • • , Sj} lies in A because those points do not lie outside C\ . Repeating this argument we construct the sequence of cycles C\, C2, ■ ■ ■ , C m , terminating with a cycle C m such that the outside of C m contains ui but none of the Si . This cycle separates uj from ip because every double-ray with a tail in w and a tail ip has to cross it to meet S. □ Using this we can prove: Lemma 3.4. Let G be a 2-connected graph with a VAP-free embedding a and more than 1 end. Then at least one of the faces of a has infinite boundary. G Proof. By Lemma |3~B1 there is a cycle C separating two ends u>, ip of G. Since a is VAP-free, both these ends lie in the same side of C, the outside say Let K u (respectively K^) be the component of G — C containing rays in w (resp. ip). Easily, it is possible to find independent subpaths P w , P/, of C such that every vertex of C adjacent with lies in P u , and similarly for and P^. Let x be an endvertex of P w ; without loss of generality, x is adjacent with K u . By the choice of x we can choose an edge e = xy with y 6 V(K U ) and a further edge f = xz incident with x with z not in K u and / not in P w , so that e, / lie on a common face boundary F . Now if F is infinite we are done, so suppose it is finite. Consider the path F' := F — C. One of the endvertices of F' is x by construction, and the other endvertex x' must also lie on P u since F' must be contained in K^UC. Now consider the cycle D contained in P'UP U . By construction, _fT w , lie in distinct sides of D. This contradicts our assumption that a is VAP-free. □ Our last lemma is Lemma 3.5. There is no 3-connected vertex-transitive VAP-free planar graph with more than 1 end. Proof. If such a graph G exists, then by Lemma 13.41 it has an infinite face- boundary. By Theorem 13.21 this implies that every vertex of G is incident with an infinite face-boundary. Thus we can pick two vertices x, y that lie in a common double ray R of G contained in a face-boundary. As G is 3-connected, there are three independent x-y paths Pi, P2, P3 by Menger's theorem [21 Theorem 3.3.1]. By an easy topo- logical argument, there must be a pair of those paths, say Pi,P2, whose union is a cycle C such that some side of C contains a tail of R and the other side of C contains P3. We may assume without loss of generality that P3 is not a single edge, for we are allowed to choose x and y far apart. Thus the side of C containing P3 contains at least one vertex z. By our previous remarks, z is incident with an infinite face-boundary. This means that both sides of C contain infinitely many vertices, contradicting our assumption that G is VAP-free. □ We can now prove the main result of this section. Proof of Theorem VS. 1\ If any of T, A is 1-cndcd then we are done since it is well- known, and not hard to prove, that all its planar Cayley graphs are VAP-free in this case. The result now follows immediately from Lemma 13.51 □ 4 VAP-free presentations via MacLane's planarity criterion In this section we derive a further characterisation of the groups that admit a flat Cayley complex by means of group presentations. We achieve this using Thomassen's Theorem 12.31 Define a VAP-free presentation to be a group presentation {S \ 1Z) with the following two properties. First, every closed walk induced by a relator R £ 1Z is a cycle; in other words, no proper subword of R is a relation. Second, for every edge e in the corresponding Cayley graph G, at most two cycles of G induced 7 by the relators in 1Z contain e. Note that the latter property can be checked by an easy algorithm once the former is guaranteed. By Lemma I!Q1 the cycles induced by the relators of a VAP-free presentation form a 2-basis. Combined with Theorem 12.31 this yields the following valuable tool, which in many cases [7] allows one to deduce that certain Cayley graphs are planar by looking only at the corresponding presentations. Corollary 4.1. A group admits a flat Cayley complex, and a VAP-free Cayley graph, if and only if it admits a VAP-free presentation. Proof. Given a planar simplified Cayley complex of the group T it is straight- forward to derive a VAP-free presentation of T. By the above discussion, such a presentation yields a VAP-free Cayley graph of T. This in turn implies that r admits a planar simplified Cayley complex by Theorem ll.il □ The fact that a group with a planar simplified Cayley complex admits a VAP-free presentation is implicit in [18l Theorem 4.5.6]. In fact, we can say a bit more. Thomassen |15l Theorem 7.4.] also proved that if G is 2-connccted, then Theorem 12.31 can be strengthened to yield that given any 2-basis B of G, there is a VAP-free embedding a of G such that B is the set of finite face-boundaries of a. If G is a Cayley graph then the requirement of being 2-connectcd can be dropped by applying the result to the maximal 2-connected subgraphs of G, which must be either Cayley graphs too or single edges corresponding to free generators. Thus we have Corollary 4.2. Given a VAP-free presentation, the corresponding Cayley graph has a VAP-free embedding the finite face-boundaries of which are precisely the cycles of G induced by the relators. Acknowledgements I am grateful to Martin Dunwoody for pointing out a shortcoming of an earlier version of the paper. References [1] O. Bogopolski. Introduction to Group Theory. EMS, Zucrich, Switzerland, 2008. [2] Q. Cui, J. Wang, and X. Yu. Hamilton circles in infinite planar graphs. J. Combm. Theory (Series B), 99(1):110-138, 2009. [3] R. Diestel. Graph Theory (4th edition). Springer- Vcrlag, 2010. [4] C. Droms. Infinite-ended groups with planar Cayley graphs. J. Group Theory, 9(4):487-496, 2006. [5] C. Droms, B. Servatius, and H. Scrvatius. Connectivity and planarity of Cayley graphs. Beitr. Algebra Geom., 39(2):269-282, 1998. [6] M.J. Dunwoody. Planar graphs and covers. Preprint. 8 [7] A. Gcorgakopoulos. The planar cubic cayley graphs. Preprint 2011. [8] A. Gcorgakopoulos. The planar cubic cayley graphs of connectivity 2. Preprint. [9] R. Halin. Zur haufungspunktfreien darstellung abzahlbarer graphen in der ebene. Archiv der Mathematik, 17:239-243, 1966. [10] A. Hatcher. Algebraic Topology. Cambrigdc Univ. Press, 2002. [11] W. Imrich. On Whitney's theorem on the unique embeddability of 3- connected planar graphs. In Recent Adv. Graph Theory, Proc. Symp. Prague 1974, pages 303-306. 1975. [12] M. Keller. Curvature, geometry and spectral properties of planar graphs. Preprint. [13] G. Kozma. Percolation, perimetry, planarity. Rev. Mat. Iberoamericana, 23(2):671-676, 2007. [14] A.M. Macbeath. The classification of non-euclidean plane crystallographic groups. Can. J. Math., 19:1192-1205, 1967. [15] C. Thomassen. Planarity and duality of finite and infinite graphs. J. Corn- bin. Theory (Series B), 29(2):244 - 271, 1980. [16] H. Whitney. Congruent graphs and the connectivity of graphs. American J. of Mathematics, 54(1):150-168, January 1932. [17] H.C. Wilkic. On non-Euclidean crystallographic groups. Math. Z., 91:87- 102, 1965. [18] H. Zieschang, E. Vogt, and H.-D. Coldewey. Surfaces and planar discontin- uous groups. Revised and expanded transl. from the German by J. Stillwell. Lecture Notes in Mathematics 835. Springer- Verlag, 1980. 9